home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 11 / Info-Mac_XI_Disc_1.cdr_ / Info-Mac XI Disc 1.cdr / Programs / Science & Math / MacEspresso 1.0 / espresso / part.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-12-10  |  2.0 KB  |  108 lines  |  [TEXT/R*ch]
  1. #include "mincov_int.h"
  2.  
  3.  
  4. static void
  5. copy_row(A, prow)
  6. register sm_matrix *A;
  7. register sm_row *prow;
  8. {
  9.     register sm_element *p;
  10.  
  11.     for(p = prow->first_col; p != 0; p = p->next_col) {
  12.     (void) sm_insert(A, p->row_num, p->col_num);
  13.     }
  14. }
  15.  
  16.  
  17. static int
  18. visit_row(A, prow, rows_visited, cols_visited)
  19. sm_matrix *A;
  20. sm_row *prow;
  21. int *rows_visited;
  22. int *cols_visited;
  23. {
  24.     sm_element *p;
  25.     sm_col *pcol;
  26.  
  27.     if (! prow->flag) {
  28.     prow->flag = 1;
  29.     (*rows_visited)++;
  30.     if (*rows_visited == A->nrows) {
  31.         return 1;
  32.     }
  33.     for(p = prow->first_col; p != 0; p = p->next_col) {
  34.         pcol = sm_get_col(A, p->col_num);
  35.         if (! pcol->flag) {
  36.         if (visit_col(A, pcol, rows_visited, cols_visited)) {
  37.             return 1;
  38.         }
  39.         }
  40.     }
  41.     }
  42.     return 0;
  43. }
  44.  
  45.  
  46. static int visit_col(sm_matrix *A, sm_col *pcol, int *rows_visited, int *cols_visited)
  47. {
  48.     sm_element *p;
  49.     sm_row *prow;
  50.  
  51.     if (! pcol->flag) {
  52.     pcol->flag = 1;
  53.     (*cols_visited)++;
  54.     if (*cols_visited == A->ncols) {
  55.         return 1;
  56.     }
  57.     for(p = pcol->first_row; p != 0; p = p->next_row) {
  58.         prow = sm_get_row(A, p->row_num);
  59.         if (! prow->flag) {
  60.         if (visit_row(A, prow, rows_visited, cols_visited)) {
  61.             return 1;
  62.         }
  63.         }
  64.     }
  65.     }
  66.     return 0;
  67. }
  68.  
  69. int
  70. sm_block_partition(A, L, R)
  71. sm_matrix *A;
  72. sm_matrix **L, **R;
  73. {
  74.     int cols_visited, rows_visited;
  75.     register sm_row *prow;
  76.     register sm_col *pcol;
  77.  
  78.     /* Avoid the trivial case */
  79.     if (A->nrows == 0) {
  80.     return 0;
  81.     }
  82.  
  83.     /* Reset the visited flags for each row and column */
  84.     for(prow = A->first_row; prow != 0; prow = prow->next_row) {
  85.     prow->flag = 0;
  86.     }
  87.     for(pcol = A->first_col; pcol != 0; pcol = pcol->next_col) {
  88.     pcol->flag = 0;
  89.     }
  90.  
  91.     cols_visited = rows_visited = 0;
  92.     if (visit_row(A, A->first_row, &rows_visited, &cols_visited)) {
  93.     /* we found all of the rows */
  94.     return 0;
  95.     } else {
  96.     *L = sm_alloc();
  97.     *R = sm_alloc();
  98.     for(prow = A->first_row; prow != 0; prow = prow->next_row) {
  99.         if (prow->flag) {
  100.         copy_row(*L, prow);
  101.         } else {
  102.         copy_row(*R, prow);
  103.         }
  104.     }
  105.     return 1;
  106.     }
  107. }
  108.